import java.util.Stack;

public class Solution {
    /**
     * 删除字符串中的所有相邻重复项
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            if (stack.isEmpty() || stack.peek() != chs[i]) {
                stack.push(chs[i]);
            } else if(stack.peek() == chs[i]) {
                stack.pop();
            }
        }
        StringBuilder ret = new StringBuilder();
        while (!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }

    /**
     * 比较含退格的字符串
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        char[] chs = s.toCharArray();
        char[] cht = t.toCharArray();
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        for(int i = 0; i < chs.length; i++) {
            if (chs[i] != '#') {
                stack1.push(chs[i]);
            } else if (chs[i] == '#' && !stack1.isEmpty()) {
                stack1.pop();
            }
        }
        for(int i = 0; i < cht.length; i++) {
            if (cht[i] != '#') {
                stack2.push(cht[i]);
            } else if (cht[i] == '#' && !stack2.isEmpty()) {
                stack2.pop();
            }
        }
        // 比较
        if (stack1.size() != stack2.size()) {
            return false;
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.pop() != stack2.pop()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 基本计算器II
     * @param s
     * @return
     */
    public int calculate(String s) {
        char[] chs = s.toCharArray();
        Stack<Integer> nums = new Stack<>(); // 存储数字
        char op = '+'; // 存储操作符
        int i = 0;
        while(i < chs.length) {
            if (chs[i] == ' ') {
                i++;
                continue;
            }
            // 操作数，压入栈中
            if (Character.isDigit(chs[i])){
                // 获取 数字
                int count = 0;
                while(i < chs.length && Character.isDigit(chs[i])) {
                    count = (chs[i] - '0') + count * 10;
                    i++;
                }
                // 直接放入
                if (op == '+') {
                    nums.push(count);
                } else if (op == '-') {
                    nums.push(-count);
                } else if (op == '*') {
                    nums.push(nums.pop() * count);
                } else if (op == '/') {
                    nums.push(nums.pop() / count);
                }
            } else {
                op = chs[i];
                i++;
            }
        }
        int ret = 0;
        while (!nums.isEmpty()) {
            ret += nums.pop();
        }
        return ret;
    }

    /**
     * 字符串解码
     * @param s
     * @return
     */
    public String decodeString(String s) {
        char[] chs = s.toCharArray();
        Stack<StringBuffer> stack = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        int i = 0, n = chs.length;
        stack.push(new StringBuffer());
        while(i < n){
            if(chs[i] >= '0' && chs[i] <= '9'){//当前字符为数字，提取数字，并将其放入栈nums中
                int num = 0;
                while(i < n && (chs[i] >= '0' && chs[i] <= '9')){
                    num = num * 10 + (chs[i] - '0');
                    i++;
                }
                nums.push(num);
            }else if(chs[i] == '['){//当前字符为[,提取字符串，并将其放入栈stack中
                i++;
                StringBuffer tmp = new StringBuffer();
                while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                    tmp.append(chs[i]);
                    i++;
                }
                stack.push(tmp);
            }else if(chs[i] == ']'){//当前字符为 ] 将k个该字符串拼接到栈顶元素后
                StringBuffer tmp = stack.pop();
                int k = nums.pop();
                while(k-- > 0){
                    stack.peek().append(tmp);
                }
                i++;
            }else{//当前字符为普通字符，将所有普通字符拼接到stack栈顶元素后
                StringBuffer tmp = new StringBuffer();
                while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                    tmp.append(chs[i]);
                    i++;
                }
                stack.peek().append(tmp);
            }
        }
        return stack.peek().toString();
    }

    /**
     * 验证栈序列
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, len = pushed.length;
        for(int x: pushed) {
            stack.push(x);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return i == len;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] pushed = {1, 2, 3, 4, 5};
        int[] popped = {4, 5, 3, 2, 1};
        solution.validateStackSequences(pushed, popped);
    }
}
